#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <array>

using namespace std;

class Solution {
private:
    const int MAXN = 401;
    array<vector<string>, 26> graph;  // 存储每个字符对应的贴纸
    unordered_set<string> visited;    // 记录已访问的状态
    queue<string> q;                  // BFS队列

    // 对字符串进行排序
    string sortStr(string str) {
        sort(str.begin(), str.end());
        return str;
    }

    // 计算使用贴纸s后得到的新目标字符串，使用std::string替代stringBuilder
    string nextStr(string t, string s) {
        string res;  // 直接使用string作为结果
        int i = 0, j = 0;
        while (i < t.length()) {
            if (j == s.length()) {
                res += t[i++];  // 直接拼接字符
            } else {
                if (t[i] < s[j]) {
                    res += t[i++];  // 直接拼接字符
                } else if (t[i] > s[j]) {
                    j++;
                } else {
                    i++;
                    j++;
                }
            }
        }
        return res;
    }

public:
    int minStickers(vector<string>& stickers, string target) {
        // 初始化图
        for (int i = 0; i < 26; i++) {
            graph[i].clear();
        }
        visited.clear();
        // 清空队列
        while (!q.empty()) {
            q.pop();
        }
        
        // 构建图：每个字符映射到包含它的贴纸
        for (string& str : stickers) {
            string sortedStr = sortStr(str);
            for (int i = 0; i < sortedStr.length(); i++) {
                // 每个贴纸只添加一次到对应字符的列表中
                if (i == 0 || sortedStr[i] != sortedStr[i-1]) {
                    graph[sortedStr[i] - 'a'].push_back(sortedStr);
                }
            }
        }
        
        // 对目标字符串排序
        string sortedTarget = sortStr(target);
        visited.insert(sortedTarget);
        q.push(sortedTarget);
        int level = 1;
        
        // BFS主循环
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                string cur = q.front();
                q.pop();
                
                // 尝试使用包含当前目标首字符的所有贴纸
                for (string& s : graph[cur[0] - 'a']) {
                    string next = nextStr(cur, s);
                    if (next.empty()) {
                        return level;  // 找到解决方案
                    } else if (visited.find(next) == visited.end()) {
                        visited.insert(next);
                        q.push(next);
                    }
                }
            }
            level++;
        }
        
        return -1;  // 无法拼出目标字符串
    }
};
